package com.ruoyi.learn.java.algorithm.graph;

import java.util.*;

public class GraphBFS {
    // 使用Map表示邻接表。Key是节点，Value是其邻居节点列表。
    private Map<Integer, List<Integer>> adjList;

    public GraphBFS() {
        adjList = new HashMap<>();
    }

    // 添加边（无向图）
    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }

    // 从起始节点start进行BFS遍历
    public void bfs(int start) {
        // 1. 创建队列用于存储待访问的节点
        Queue<Integer> queue = new LinkedList<>();

        // 2. 创建Set用于记录已访问的节点
        Set<Integer> visited = new HashSet<>();

        // 3. 将起始节点加入队列，并标记为已访问
        queue.offer(start);
        visited.add(start);

        System.out.println("BFS Traversal starting from node " + start + ":");
        // 4. 循环直到队列为空
        while (!queue.isEmpty()) {
            // 5. 从队列头部取出一个节点
            int current = queue.poll();
            // 6. 访问（处理）当前节点
            System.out.print(current + " ");

            // 7. 获取当前节点的所有邻居
            List<Integer> neighbors = adjList.get(current);
            if (neighbors != null) { // 检查节点是否存在邻居
                for (int neighbor : neighbors) {
                    // 8. 如果邻居未被访问过
                    if (!visited.contains(neighbor)) {
                        // 9. 将其加入队列，并立即标记为已访问
                        queue.offer(neighbor);
                        visited.add(neighbor);
                    }
                }
            }
        }
        System.out.println(); // 换行
    }

    // 示例用法
    public static void main(String[] args) {
        GraphBFS graph = new GraphBFS();
        // 构建一个简单的无向图
        //      1
        //     / \
        //    2   3
        //   / \   \
        //  4   5   6
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 6);

        // 从节点1开始BFS
        graph.bfs(1); // 输出: 1 2 3 4 5 6
    }
}